package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC229 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
         * @param 此题目参考了别人代码
         * 这是因为问题情况较为复杂
         * 经典的摩尔投票，值得学习
         * @return:
         */
    class Solution {

        public List<Integer> majorityElement(int[] nums) {
            return getKCandidates(nums, 2);
        }

        public List<Integer> getKCandidates(int[] arr, int k) {
            List<Integer> res = new ArrayList<>();
            if (arr == null || arr.length == 0) {
                return res;
            }

            // 定义候选者和它们的票数
            int[] candidates = new int[k];
            int[] candidateCounts = new int[k];
            for (int i = 0; i < k; i++) candidates[i] = arr[0];

            // 投票过程
            for (int num : arr) {
                boolean flag = false;
                for (int i = 0; i < k; i++) {
                    if (num == candidates[i]) {
                        ++candidateCounts[i];//投票给候选人i
                        flag = true;
                        break;
                    }
                }

                if (!flag) {
                    boolean flag2 = false;
                    for (int i = 0; i < k; i++) {
                        if (candidateCounts[i] == 0) {
                            candidates[i] = num;//重新选择候选人为num
                            ++candidateCounts[i];
                            flag2 = true;
                        }
                    }

                    if (!flag2)
                        // 当前都未被投票并且票数大于0，则减票数
                        for (int i = 0; i < k; i++) --candidateCounts[i];
                }
            }

            // 检查票数是否符合
            for (int i = 0; i < k; i++) candidateCounts[i] = 0;
            for (int num : arr) {
                for (int i = 0; i < k; i++) {
                    if (num == candidates[i]) {
                        ++candidateCounts[i];
                        break;
                    }
                }
            }

            for (int i = 0; i < k; i++) {
                if (candidateCounts[i] > arr.length / (k + 1)) res.add(candidates[i]);
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2]");
        System.out.println(solution.majorityElement(arr));
    }

    public static void main(String[] args) throws Exception {
        LC229 an = new LC229();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
